AVL tree stands for Adelson-Velsky and Landis tree, and it is a self-balancing Binary Search Tree. AVL tree is the extension of the BST data structure. Also, it reduces the time complexity of the many operations of BST. The tree data structure got its name from the name of its inventors, i.e., Adelson-Velsky and Landis. They published the algorithm in 1962. In a binary search tree, searching and inserting can have the complexity of O(n), where n represents the number of nodes. However, with the AVL tree, we can do it with a time complexity of O(log n), which makes it more efficient and faster than a BST. We said that AVL tree is a self-balancing binary search tree, but what does it mean? A tree will be considered as a balanced tree if the difference of the heights of its right subtree and left subtree is between -1 to 1. Self-balancing is a property that helps a tree data structure to form a balanced tree. The height difference of two subtrees is known as the Balance Factor. With every insertion and deletion operation, the AVL tree performs the self-balancing property, which makes the tree data structure a balanced tree. As the AVL tree is an extension of the binary search tree, it satisfies the BST properties, which are that the key value of the left child should be smaller than the parent and the key value of the right child should be greater than the parent.
AVL Tree
Balancing Factor
The Balancing Factor determines whether the tree is balanced or not. If the value of the Balancing Factor is between -1 to 1, then the tree would be considered as a balanced tree. Else, it will be an unbalanced tree. If, after the insertion or deletion operation in an AVL tree, the Balancing Factor becomes more than 1 or less than -1, then the algorithm for self-balancing will balance the tree. The Balancing Factor shows the difference between the height of the left subtree and the right sub-tree.
Balancing Factor = height(Right Sub-Tree) – height(left sub-tree)
The following table gives out information on what the different values of the Balancing Factor mean:
| Balance Factor Values | Description |
| Balance Factor <= -1 | It means the height of the left subtree is larger than the right subtree. |
| Balancing Factor = 0 | The height of the left subtree is equal to the height of the right subtree. |
| Balancing Factor >=1 | The height of the right subtree is greater than the height of the left subtree. |
Complexity
AVL reduces the time complexity of BST for search, insert and delete operations. The following table gives out the various complexities of the self-balancing BST in average and worst cases:
| Algorithm | Average case | Worst case |
| Space | o(n) | o(n) |
| Search | o(log n) | o(log n) |
| Insert | o(log n) | o(log n) |
| Delete | o(log n) | o(log n) |
AVL Tree Rotation
In AVL, after an insertion or deletion operation, we check for the Balancing Factor. If it is in between -1 to 1, then we leave the tree. Otherwise, we have to balance the tree. To balance the tree, we need to rotate the positioning of the nodes after the insertion or deletion operation. We move the nodes either left or right in order to make the tree a balanced tree. In AVL, we have a total of four types of rotation that are classified into two types:
-
Single Rotation
- Left Rotation
- Right Rotation
-
Double Rotation
- Left-Right Rotation
- Right-Left Rotation
1. Single Rotation
a. Single Left Rotation In Single Left Rotation, each node is moved to its left from the current position.
Example:
10 20
\ / \
20 ----> 10 30
\
30
b. Single Right Rotation In this rotation, each node moves to its right from the current position.
Example:
30 / 20 ------------> 20 / / \ 10 10 30
2. Double Rotation
a. Left-Right Rotation In this, we first rotate the node left and then right with respect to the current position.
Example:
30 30
/ /
10 ----> 20 --------> 20
\ / / \
20 10 10 30
b. Right-Left Rotation In this type of double rotation, the node moves to the right then to the left w.r.t. to the current position.
Example:
10 1 \ \ 30 ---------> 2 -----------------> 20 / \ / \ 20 3 10 30
Self-balancing AVL Tree vs. Binary Search Tree
| AVL Tree | Binary Search Tree |
| First Step - Insert Root Node 10 | |
10 / \ / \ |
10 / \ / \ |
| Second Step - Insert 30 | |
10
/ \
/ \
30
|
10 / \ / \ 30 |
| Third Step - Insert 40 | |
10
\
\
30
\
40
Self-balancing by rotation because the height of the right child is 2 and the height of the left child is 0, so the difference is not between -1 to 1.
30 / \ / \ 10 40 |
10
\
\
30
\
40
|
Conclusion
An AVL (Adelson-Velsky and Landis) tree is simply a binary search tree that is self-balancing. It offers a more efficient way of searching and inserting elements in a tree data structure.
People are also reading: